package com.yang.Dp;

/**
 * @Author: yang
 * @Description:
 * @Date: Created in 18:14 2022/8/9
 * @Modified By:
 */
public class LeetCode343 {
    public static void main(String[] args){
        LeetCode343Solution leetCode343Solution = new LeetCode343Solution();
        int i = leetCode343Solution.integerBreak(10);
        System.out.println(i);
    }
}
class LeetCode343Solution {
    public int integerBreak(int n) {
        // 1.确定dp 以及 dp下标含义 dp[i]表示当前正整数i拆分相乘最大值
        // 2.确定递推公式 有这么几个方法得到 j*(i - j)(拆成两个数)  j*dp[i - j](拆分为多个数)
        // 3.数组初始化  正确的来讲dp[0]dp[1]不应该进行初始化 因为0和1无法被拆分
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            // i - j 而不是i - 1因为再大其实也就是重复了
            for (int j = 1; j <= i - j; j++) {
                dp[i] = Math.max(j * (i - j), Math.max(dp[i], j * dp[i - j]));
            }
        }
        return dp[n];
    }
}
